package 数据结构.LinkList.diamond;

//LeetCode19 删除链表的倒数第 N 个节点
// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//方法：先得到链表的长度再进行操作【虽然还是遍历了两次链表】
//              因为要删除倒数第n个，利用size-n就可以得到正向时是第几个了
//todo：要点：利用两个节点位置【一个记录前，一个记录后】
public class removeNthFromEnd {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    // 打印链表
    public static void printList(ListNode head) {
       ListNode node=head;
       while (node!=null){
           System.out.print(node.val+"-->");
           node=node.next;
       }
    }

    public static void main(String[] args) {
        ListNode head=new ListNode(2);
        ListNode two=new ListNode(3);
        ListNode three=new ListNode(4);
        ListNode four=new ListNode(5);
        head.next=two;
        two.next=three;
        three.next=four;
        ListNode listNode = removeNthFromEnd(head,2);
        printList(listNode);
    }
        public static ListNode removeNthFromEnd(ListNode head, int n) {
        //输出倒数第几个节点 n为，下次：比如2 则要删除倒数第2个：
            //没有长度：2--3--4--5--6
            ListNode tem=head;
            //todo：记录前面那个节点【方便跳过下面的当前节点 front=pre.next 就是删除pre节点了】
            ListNode front=head;
            //记录当前那个节点
            ListNode pre=head.next;
            int size=0;
            while (tem!=null){
                tem=tem.next;
                size++;
            }
            int tar=size-n;
            int s2=1;
            if(tar==0){
                head=head.next;
                return head;
            }
            while (pre!=null){
                if(s2==tar){
                    front.next=pre.next;
                    return head;
                }
                front=front.next;
                pre=pre.next;
                s2++;
            }
            return head;
    }
}
